You may also want to look at changing the user's name in everyone else's buddy list. Their list will still have the old name and will not resolve until they re-add the new name or you use a tool that changes the name in the vpuserinfo database.
TOOL: Sametime (IBM Lotus Instant Messaging and Web Conferencing 3.x NAME CONVERSION UTILITY English)
http://www14.software.ibm.com/webapp/download/product.jsp?cat=&fam=&s=z&id=MBEN-53VLVF&pf=&k=ALL&q=&dt=&v=&rs=&S_TACT=104AH+W42&S_CMP=&sb=r&sr=7